import java.util.PriorityQueue;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //最后一块石头的重量2
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += stones[i];
        }
        int key = sum/2;
        int[][] dp = new int[n+1][key+1];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= key; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=stones[i-1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return sum-2*max;
    }

    //（空间优化版本）
    public int lastStoneWeightII2(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += stones[i];
        }
        int key = sum/2;
        int[] dp = new int[key+1];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = key; j >=1; j--) {
                if(j>=stones[i-1]) {
                    dp[j] = Math.max(dp[j], dp[j-stones[i-1]]+stones[i-1]);
                }
                max = Math.max(max, dp[j]);
            }
        }
        return sum-2*max;
    }

    //最后一块石头的重量1
    public int lastStoneWeight(int[] stones) {
        int n = stones.length;
        PriorityQueue<Integer> queue = new PriorityQueue<>((i, j)->{
            return j-i;
        });
        for (int i = 0; i < stones.length; i++) {
            queue.add(stones[i]);
        }
        while(queue.size()>1) {
            int a = queue.poll();
            int b = queue.poll();
            if(a!=b) {
                queue.add(a-b);
            }
        }
        return queue.isEmpty()?0:queue.poll();
    }
}
